Various methods and systems to generate a dictionary for coding and decoding signals are possible, and particularly, methods and systems may produce a large dictionary of atoms having the desirable properties of weak mutual coherence, weak autocorrelation and a small supremum (the supremum is sometimes referred to as the peak-to-average power ratio).
Digital signals, or simply signals, can be thought of as functions of a finite number of elements. The elements may be spaced along a line (single-dimensional), along a plane (two-dimensional) in space (three-dimensional) or in a hyper-space (multi dimensional). For example, in one-dimension we will consider Fq the finite line namely the finite field with q elements indexed by time t. The space of signals H=C(Fq) is a Hilbert space equipped with a natural Hermitian product
      〈          ϕ      ,      φ        〉    =            ∑              i        ∈                  F          q                      ⁢          ϕ      ⁢                          ⁢              (        t        )            ⁢                          ⁢                        φ          ⁡                      (            t            )                          _            for two signals φ, φεH.
A central problem is constructing useful classes of signals that demonstrate strong descriptive power and at the same time are characterized by formal mathematical conditions. Meeting these two requirements is a non-trivial task and is a source for many novel developments in the field of signal processing. The problem was tackled, over the years, by various approaches. In the classical approach, a signal is characterized in terms of its expansion with respect to a specific basis. A standard example of this kind is the class of limited band signals, which is defined using the Fourier basis and consists of signals with a specified support of their Fourier representation.
However, for certain applications this approach is too restrictive. In a more general approach, the signal is characterized in terms of its expansion with respect to a frame, which is kind of a generalized basis. The theory of wavelets is a particular application of this approach (see U.S. Pat. No. 7,272,599 issued to Gilbert, et al.). As it turns out, many classical results from linear algebra have appropriate generalizations to the setting of frames, as a consequence, wavelets analysis exhibit structural similarity to Fourier analysis.
Recently, (e.g. U.S. Pat. No. 7,271,747 issued to Baraniuk, et al.) a novel approach was introduced, hinting towards a fundamental change of perspective about the nature of signals. This new approach uses the notion of a dictionary, which is yet another kind of generalized basis. The basic idea is the same as before, namely, a signal is characterized in terms of its expansion as a linear combination of vectors in the dictionary. Each vector in the dictionary is called an atom. The main difference is that the characterization is intrinsically non-linear, hence as a consequence, one comes to deal with classes of signals which are not closed with respect to addition. More formally a dictionary is a set D of atoms Si (in some of the literature listed herein [e.g. Gurevich, S., “Weil Representation, Deligne Sheaf and Proof of the Kurtberg-Rudnick Conjecture”, Thesis submitted for the degree “Doctor of Philosophy” University of Tel-Aviv, available at arXiv:math-ph/0601031 v1 15 Jan. 2006] the dictionary D is referred to as a system S and the atoms are referred to as signals) for the sake of discussion herein the symbols D and D are the same and the symbols Fq and Fq are the same.
A very simple example of a dictionary 110 is illustrated in FIG. 1. Dictionary 110 may be thought of as a matrix having L columns each column being an atom Si 115a-v, which is a q-length vector. In the example of FIG. 1, q=11 and L=22. A signal 120 (which can be thought of as a q-length vector) is the product of dictionary 110 and a vector of coefficients 130. The rank of dictionary 110 and the length of vector 120 are q. Necessarily, q≦L. The atoms are normalized i.e. kSik2=1. It is clear that if q<L a single signal may be represented in more than one way and thus coefficients a1 . . . aL are not unique. One idea is to find the sparsest possible representation of
  ψ  =            ∑              S        ∈        D              ⁢                  ⁢                  a        s            ⁢      S      (sparse meaning having few non-zero coefficients).
In the example of FIG. 1 atoms 115a-k (Ss0 through Ss10) are the standard basis of F11 i.e. Ssj=δ(t−τj) for τj2F11 i.e. j=(0, 1, 2, 3 . . . 10). Atoms 1151-v (Sf0 through Sf10) are the Fourier basis Sfj=q−1/2exp(i2πωjt/q) where i is the square root of −1 and ωj, tj2Fq and as stated before in the example of FIG. 1, q=11. Clear each basis Ssi (atoms 115a-k) and Sfj (atoms 1151-v) span F11. Therefore the coefficient vector (a1, . . . , a22) is not unique: We can express a vector ψ in many ways. For example in FIG. 2a a signal 220a ψ=α1δ(t−4)+α1q−1/2 cos(2π3t/q) is illustrated in terms of the standard basis (thus each asterisk in the FIG. 2a,b represents the value of the coefficient ai for i={0, 1, 2, 3, . . . , 10} given by the x-axis and aj=0 for j={11, 12, 13 . . . 21}. Alternatively, in FIG. 2b we can express the signal 220b ψ in the Fourier basis. The Fourier transform of ψis {circumflex over (ψ)}(f)=α1q−1/2 cos(2πτf/q)+α2δ(f−ω), thus the to express ψ in the Fourier basis we set a0, . . . , a10=0 and set a11, . . . , a21 the numbers shown by the asterisk in FIG. 2b. In either case (the coefficients of the standard basis in FIG. 2a or of the Fourier basis FIG. 2b) representing signal 220a,b ψ requires 11 non-zero coefficients. On the other hand using our entire dictionary 110 we find that ψ=α1Ss5+α2Sf4 and thus can be represented by the coefficient vector {0,0,0,0,α1,0,0,0,0,0,0,0,0,0,0,α2,0,0,0,0,0,0}. Finding this sparse representation has great value in signal analysis (for example in Code Division Multiple Access CDMA if two transmitters are transmitting simultaneously, the coefficients of the sparse representation are the clean signals of each of the transmitters; similarly in data compression, the sparse representation is the most efficient way to store the data). The obvious goal then is to find the largest possible dictionary from which we can find a unique sparse representation of a large class of signals.
The first question that needs to be addressed is, given a representation of a signal, whether it is the sparsest representation or is there an alternative sparse or sparser representation. The mathematical tools to answer this question are as follows. The dictionary D is called an N-independent set if every subset D′⊂D, with N elements jD′j=N, is linearly independent. Given a 2N-independent set D, every signal ψ2H, has at most one representation of the form
  ψ  =            ∑              S        ∈                  D          ′                      ⁢                  a        s            ⁢              S        .            D′⊂D, with jD′j≦N. Such a representation, if exists, it is unique and is called the sparse representation. Consequently another name for such a set D is an N-sparse dictionary. Given that a signal ψ admits a sparse representation, it is natural to ask whether the coefficients as can be effectively reconstructed. A dictionary D for which there exists a polynomial time algorithm for reconstructing the “sparse” coefficients is called an effectively N-sparse dictionary. As an example in CDMA if one has an effectively N-sparse dictionary with q3 atoms, one can assign a separate code to q3 users and at any given time and place as many as N users may simultaneously transmit without significant interference.
To give some feeling for the new concept, we note that an orthonormal basis appears as a degenerate example of an effectively sparse dictionary. More precisely, it is dimH-sparse, consisting of dimH atoms. The effectiveness follows from the fact that the coefficient as can be reconstructed from a signal ψ by as=hS; ψi.
A basic problem in the new theory is introducing systematic constructions of “good” effectively N-sparse dictionaries. Here “good” means that the size of the dictionary and the sparsity factor N are made as large as possible. Currently, the only known methods use either certain amount of randomness or are based on ad-hoc considerations.
Showing that a dictionary is effectively N-sparse is difficult. A way to overcome this difficulty is to introduce the stronger notion of weakly correlated dictionaries. A dictionary D is called “-correlated for 0≦”<<1 if for every two different atoms Si≠Sj2 D we have jhSi,Sjij≦”. The two notions of correlation and sparsity are related by the following proposition: If D is 1/R-correlated then D is effectively R/2-sparse.
The final question is whether it is possible to find the sparse representation. The tools to answer this question are also available in mathematics. In general if there exists a representation of a signal
  ψ  =            ∑              i        =        1            N        ⁢                  a        i            ⁢              S        i            such that N<(2−1/2−0.5)/μ where μ is the maximum cross-covariance μ=maxi,j|Si,Sj|, then the representation is unique and can be found using known minimization and optimization routines that are commercially available for example in MATLAB® matrix operation package and particularly using the signals and optimization toolboxes (more details on this are available in the manual to MATLAB® and in the literature for example see Tropp, J. A., Just Relax: Convex Programming Methods for Identifying Sparse Signals in Noise, IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 3, pp 1030-1051, MARCH 2006)
Thus, given a dictionary D, there are various desired properties which appear in the engineering wish list [e.g. see Howard, S. D.; Calderbank, A. R.; Moran, W. “The finite Heisenberg-Weyl groups in radar and communications”. EURASIP JOURNAL ON APPLIED SIGNAL PROCESSING Art. No. 85685 2006 (2006); Golomb S. W. and Gong G., Signal design for good correlation. For wireless communication, cryptography, and radar. Cambridge University Press, Cambridge (2005); W. Miller, “Topics in harmonic analysis with applications to radar and sonar,” in Radar and Sonar, Part I, R. Blahut, W. Miller, and C. Wilcox, Eds., IMA Volumes in Mathematics and Its Applications, Springer, New York, N.Y., USA, 1991; L. Auslander and R. Tolimieri, “Radar ambiguity functions and group theory,” SIAM Journal on Mathematical Analysis, vol. 16, no. 3, pp. 577-601, 1985; M. S. Richman, T. W. Parks, and K. G. Shenoy, “Discrete-time, discrete-frequency, time-frequency analysis,” IEEE Transactions on Signal Processing, vol. 46, no. 6, pp. 1517-1527, 1998.]. For example, in various situations one requires that the atoms will be weakly cross-correlated, i.e., that for any two atoms Si6=Sj2 D jSi; Sjj<<1; this property is trivially satisfied if D is an orthonormal basis. Such a system cannot consist more then dimH atoms, however, for certain applications, [e.g., CDMA as explained by Viterbi A. J., CDMA: Principles of Spread Spectrum Communication. Addison-Wesley Wireless Communications (1995).] a larger number of atoms is desired, in that case the orthogonality condition is relaxed.
During the transmission process, an atom S might be distorted in various ways. Two basic types of distortions are time shift S(t) 7! LτS(t)=S(t+τ) and phase shift S(t) 7! MωS(t)=exp(2πiωt/q) S(t), where τ; ω 2 Fq. The first type appears in asynchronous communication and the second type is a Doppler effect due to relative velocity between the transmitting and receiving antennas. In conclusion, a general distortion is of the type S7! MωLτS; suggesting that for every Si 6=Sj 2 D it is natural to require the following stronger condition that both the autocorrelation and the cross correlation for all atoms under a general distortion be small jSi; MωLτSjj<<1 for all ω,τ2 Fq and for all Si, Sj 2 D (that is to say whether i=j or i 6=j); Also in radar from the time translation of a reflected signal it is possible to identify the distance to the target and from the frequency modulation of the reflected signal it is possible to determine the speed at which the target is approaching/being approached. Thus in radar it is desirable to have a system that is sensitive to these distortions so that by optimization one can determine the distortion and thus location and velocity of the target.
Due to technical restrictions in the transmission process, signals are sometimes required to admit low peak-to-average power ratio [for an explanation of this requirement see Paterson, K. G. and Tarokh V., “On the existence and construction of good codes with low peak-to-average power ratios”. IEEE Trans. Inform. Theory 46 (2000).], i.e., low peak-to-average power ratios means that for every normalized S2D max fjS(t)j: t2Fpg<<1 (normalized means that kSk2=1):
Finally, several schemes for digital communication require Fourier invariance, which means that the above properties will continue to hold also if we replace atoms from D by their Fourier transform:
To find a dictionary that spans a signal space and has the desired properties, it is necessary to use a few results from representation theory. A group is a set of elements and a multiplication rule such that the set is closed under multiplication, a neutral element with respect to the multiplication belongs to this set and that for each element its inverse belongs to the set. An example is the set of unitary operators on the Filbert space of functions over the finite field Fq where q is a power of a prime number {a unitary operator acts on a member of the Hilbert space and assigns it to another member of the Hilbert space}. We denote the Hilbert space by H(Fq), and the group of unitary operators on that Hilbert space by U(H(Fq)). The multiplication is the composition. In a given coordinate system these operators are q£q matrices and the multiplication is the usual matrix multiplication. An Abelian group is a commutative group g1g2=g2g1. An Abelian subgroup of U(H(Fq)) can be diagonalized together by a single set of eigenvectors Si. These eigenvectors span the Hilbert space.
An example of an Abelian group is the set of time shifts L(τi) [L(τi) is the same as Lτ above] for all τiεFq where L(τi)Si(t)=Si(t+τi). It is clear that time shifting is commutative {L(τ1)L(τ2)Si(t)=L(τ2)L(τ1)Si(t)}. The Abelian group of time shifts may be written as a q£q matrix where the (j,k) matrix element is (L(τi))jk=δ (τj−τk+τi) where δ (x)=1 if x=0 mod q and 0 otherwise. The eigenvectors of this matrix are the vectors Sfi=q−1/2exp(i2πωit/q) that we defined previously because L(τ)Sfj(t)=λj(τ)Sfj(t) where λj(τ)=q−1/2exp(i2πωjτ/q). Similarly the group of frequency modulations M(ω)Si(t)=exp(2πiωt/q)Si(t) has as its eigenvectors the vectors SSj=δ(t−τj) because M(ω))Si(t)=λj(ω)Sfj(t) where λj(ω)=q−1/2exp(i2πωτj/q) [the terminology M(ω) and Mω refer to the same frequency shift].
Continuous Heisenberg-Weyl groups have long been applied to interpret radar signals [e.g. see U.S. Pat. No. 5,831,934 issued to Gill et al.; W. Miller, “Topics in harmonic analysis with applications to radar and sonar,” in Radar and Sonar, Part I, R. Blahut, W. Miller, and C. Wilcox, Eds., IMA Volumes in Mathematics and its Applications, Springer, New York, N.Y., USA, 1991; L. Auslander and R. Tolimieri, “Radar ambiguity functions and group theory,” SIAM Journal on Mathematical Analysis, vol. 16, no. 3, pp. 577-601, 1985]. More recently it has been suggested that finite Heisenberg-Weyl groups could be useful building a dictionary for digital radar and communication [Howe R., “Nice error bases, mutually unbiased bases, induced representations, the Heisenberg group and finite geometries”. Indag. Math. (N.S.) 16: no. 3-4, 553.583 (2005); Howard, S. D.; Calderbank, A. R.; Moran, W. “The finite Heisenberg-Weyl groups in radar and communications”. EURASIP JOURNAL ON APPLIED SIGNAL PROCESSING Art. No. 85685 2006 (2006).]
The Heisenberg dictionary DH is constructed using the representation theory of the finite Heisenberg group. For a digital signal having q elements the Heisenberg dictionary contains of the order of q2 atoms and is q−1/2 correlated.
To form the Heisenberg dictionary rather than taking separately frequency modulations and time translations (making a dictionary having 2q atoms as in the example of FIGS. 1, 2a and 2b), the translation and modulations are conjugated. This conjugation produces 2D q×q array of combinations of time translations and frequency modulations. It is not trivial to make a homomorphism from the time frequency plane Fq×Fq that consists of q2 couples (τ,ω) to unitary operators on a the corresponding Hilbert space of q-dimensional signals. There is nevertheless a well known homomorphism Π(τ,ω,z)=exp[(πiτω+2z)/q)MωLτ with the group law (τ1,ω1,z1)·(τ2,ω2,z2)=(τ1τ2, ω1+ω2,z1+z2+(τ1ω2−τ2ω1)/2). As stated above, a set of unitary operators can be found spanning an Abelian group (a set with a commutative multiplication law). The Heisenberg group law is not commutative because (τ1ω2−τ2ω1)≠(τ2ω1−τ1ω2). Nevertheless, for a subgroup of the Fq×Fq plane where τ2ω1−τ1ω2=0 the law is commutative. Furthermore, for a given τ2,ω2 then the law is commutative along the line ω1=τ1ω2/τ2 through the origin. More generally, any line through the origin is a commutative subspace in the Heisenberg representation. Therefore, we can choose a set of (q+1) lines through the origin and on each of those lines choose a set of q eigenvectors and the total set of all q(q+1) eigenvectors forms a Heisenberg dictionary that spans the entire Hilbert space of signals.
As it turns out, the Heisenberg dictionary has the following properties: The dictionary has q(q+1) signals. The autocorrelation is 1 for modulation/translation that is a characteristic function of a line passing through the origin (an Abelian subgroup of the Heisenburg representation) 0 otherwise. The cross correlation is 1 for two signals on a line passing through the origin and zero otherwise. The supremum is q−1/2. Thus it is possible to identify the line through the origin in the time/frequency plane to which the signal belongs. This is useful but not optimal in radar because it is difficult to determine the location and the velocity of a target independently. Similarly in communication this leads to interference between some signals of the system. The ambiguity function is a measure of signal interference (or specificity of identification for radar). Thus the ambiguity function of the Heisenberg system (illustrated in FIG. 3) instead of sharp peak has a linear ridge along a line crossing the origin. It is preferable to have a symmetric peak, thus for example U.S. Pat. No. 6,278,686 issued to Alard reveals a method to reshape an ambiguity function to achieve symmetry.
There is thus a widely recognized need for, and it would be highly advantageous to have a large dictionary of atoms having the desirable properties of a small normalized peak-to-average power ratio, weak cross correlation (both of pure atoms and of atoms that have undergone time translation or frequency modulation), and weak autocorrelation under time translation or frequency modulation.